package problems

import (
	"math"
	"sort"
	"strings"
)

// 703
// https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/
type KthLargest struct {
	nums []int
	k    int
}

func KthLargestConstructor(k int, nums []int) KthLargest {
	sort.Ints(nums)
	kl := KthLargest{make([]int, k), k}
	for k := range kl.nums {
		kl.nums[k] = math.MinInt64
	}
	ss, ds := len(nums)-k, 0
	if ss < 0 {
		ss, ds = 0, k-len(nums)
	}
	copy(kl.nums[ds:], nums[ss:])
	return kl
}

func (k *KthLargest) Add(val int) int {
	index := k.Search(val)
	if index == 0 {
		k.nums[0] = val
	} else if index > 0 {
		copy(k.nums[:index], k.nums[1:index+1])
		k.nums[index] = val
	}
	return k.nums[0]
}

func (k *KthLargest) Search(val int) int {
	if val >= k.nums[k.k-1] {
		return k.k - 1
	}
	if val <= k.nums[0] {
		return -1
	}
	l, r, m := 0, k.k-1, 0
	for l <= r {
		m = (l + r) / 2
		if k.nums[m] == val {
			return m
		}
		if k.nums[m] < val {
			l = m + 1
		} else {
			r = m - 1
		}
	}
	if k.nums[m] > val {
		return m - 1
	}
	return m
}

// 704
// https://leetcode-cn.com/problems/binary-search/submissions/
func Search3(nums []int, target int) int {
	l, r := 0, len(nums)-1
	for l <= r {
		m := (l + r) / 2
		if nums[m] == target {
			return m
		}
		if nums[m] < target {
			l = m + 1
		} else {
			r = m - 1
		}
	}
	return -1
}

// 705
// https://leetcode-cn.com/problems/design-hashset/submissions/

type MyHashSet struct {
	nums [769]*MyHashSetNode
}
type MyHashSetNode struct {
	Val  int
	Next *MyHashSetNode
}

func MyHashSetConstructor() MyHashSet {
	return MyHashSet{nums: [769]*MyHashSetNode{}}
}

func (m *MyHashSet) Add(key int) {
	hashKey := key % 769
	if m.nums[hashKey] == nil {
		m.nums[hashKey] = &MyHashSetNode{Val: key}
	} else {
		node := m.nums[hashKey]
		for node != nil {
			if key == node.Val {
				return
			}
			if node.Next == nil {
				node.Next = &MyHashSetNode{Val: key}
			}
			node = node.Next
		}
	}
}

func (m *MyHashSet) Remove(key int) {
	hashKey := key % 769
	if m.nums[hashKey] == nil {
		return
	} else {
		var pre *MyHashSetNode
		node := m.nums[hashKey]
		for node != nil {
			if key == node.Val {
				if pre == nil {
					m.nums[hashKey] = node.Next
				} else {
					pre.Next = node.Next
				}
				break
			}
			pre, node = node, node.Next
		}
	}
}

func (m *MyHashSet) Contains(key int) bool {
	hashKey := key % 769
	if m.nums[hashKey] == nil {
		return false
	} else {
		node := m.nums[hashKey]
		for node != nil {
			if key == node.Val {
				return true
			}
			node = node.Next
		}
	}
	return false
}

// 706
// https://leetcode-cn.com/problems/design-hashmap/submissions/
type MyHashMapNode struct {
	Key, Val int
	Next     *MyHashMapNode
}

type MyHashMap struct {
	Nodes [769]*MyHashMapNode
}

func MyHashMapConstructor() MyHashMap {
	return MyHashMap{Nodes: [769]*MyHashMapNode{}}
}

func (m *MyHashMap) Put(key, value int) {
	hashKey := key % 769
	if m.Nodes[hashKey] == nil {
		m.Nodes[hashKey] = &MyHashMapNode{Key: key, Val: value}
	} else {
		node := m.Nodes[hashKey]
		for node != nil {
			if key == node.Key {
				node.Val = value
				return
			}
			if node.Next == nil {
				node.Next = &MyHashMapNode{Key: key, Val: value}
			}
			node = node.Next
		}
	}
}

func (m *MyHashMap) Get(key int) int {
	hashKey := key % 769
	if m.Nodes[hashKey] != nil {
		node := m.Nodes[hashKey]
		for node != nil {
			if key == node.Key {
				return node.Val
			}
			node = node.Next
		}
	}
	return -1
}

func (m *MyHashMap) Remove(key int) {
	hashKey := key % 769
	if m.Nodes[hashKey] != nil {
		var pre *MyHashMapNode
		node := m.Nodes[hashKey]
		for node != nil {
			if key == node.Key {
				if pre == nil {
					m.Nodes[hashKey] = node.Next
				} else {
					pre.Next = node.Next
				}
				break
			}
			pre, node = node, node.Next
		}
	}
}

// 709
// https://leetcode-cn.com/problems/to-lower-case/submissions/
func ToLowerCase(str string) string {
	b := []byte(str)
	for k, v := range b {
		if v >= 'A' && v <= 'Z' {
			b[k] = v + 32
		}
	}
	return string(b)
}

// 717
// https://leetcode-cn.com/problems/1-bit-and-2-bit-characters/submissions/
func IsOneBitCharacter(bits []int) bool {
	l := 0
	for l < len(bits)-1 {
		if bits[l] == 1 {
			l += 2
		} else {
			l += 1
		}
	}
	return l == len(bits)-1
}

// 724
// https://leetcode-cn.com/problems/find-pivot-index
func PivotIndex(nums []int) int {
	if len(nums) == 0 {
		return -1
	}
	if len(nums) == 1 {
		return 0
	}
	l, r := 0, 0
	for _, v := range nums {
		r += v
	}
	for k, v := range nums {
		if l == r-v {
			return k
		}
		l, r = l+v, r-v
	}
	return -1
}

// 728
// https://leetcode-cn.com/problems/self-dividing-numbers/
func SelfDividingNumbers(left int, right int) []int {
	isDivideing := func(num int) bool {
		m, nums := num, []int{}
		for m > 0 {
			if m%10 == 0 {
				return false
			}
			nums, m = append(nums, m%10), m/10
		}
		for _, v := range nums {
			if num%v != 0 {
				return false
			}
		}
		return true
	}
	res := make([]int, 0)
	for i := left; i <= right; i++ {
		if isDivideing(i) {
			res = append(res, i)
		}
	}
	return res
}

// 733
// https://leetcode-cn.com/problems/flood-fill/
func FloodFill(image [][]int, sr int, sc int, newColor int) [][]int {
	m, n, src := len(image), len(image[0]), image[sr][sc]
	var dfs func(x, y int)
	dfs = func(x, y int) {
		if image[x][y] != src {
			return
		}
		image[x][y] = 65536
		if x > 0 {
			dfs(x-1, y)
		}
		if x < m-1 {
			dfs(x+1, y)
		}
		if y > 0 {
			dfs(x, y-1)
		}
		if y < n-1 {
			dfs(x, y+1)
		}
	}
	dfs(sr, sc)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if image[i][j] == 65536 {
				image[i][j] = newColor
			}
		}
	}
	return image
}

// 744
// https://leetcode-cn.com/problems/find-smallest-letter-greater-than-target/
func NextGreatestLetter(letters []byte, target byte) byte {
	var min, res byte = 'z' + 1, 'z' + 1
	for _, v := range letters {
		if min > v {
			min = v
		}
		if v > target && v < res {
			res = v
		}
	}
	if res == 'z'+1 {
		return min
	}
	return res
}

// 746
// https://leetcode-cn.com/problems/min-cost-climbing-stairs/
func MinCostClimbingStairs(cost []int) int {
	min, n := math.MaxInt64, len(cost)
	for i := 0; i < n; i++ {
		if i >= 2 {
			if cost[i-1] > cost[i-2] {
				cost[i] += cost[i-2]
			} else {
				cost[i] += cost[i-1]
			}
		}
		if i >= n-2 && min > cost[i] {
			min = cost[i]
		}
	}
	return min
}

// 747
// https://leetcode-cn.com/problems/largest-number-at-least-twice-of-others/
func DominantIndex(nums []int) int {
	max1, max2, index := -1, -1, 0
	for i := 0; i < len(nums); i++ {
		if nums[i] >= max1 {
			max1, max2, index = nums[i], max1, i
		} else if nums[i] >= max2 {
			max2 = nums[i]
		}
	}
	if max1 >= max2*2 {
		return index
	}
	return -1
}

// 748
// https://leetcode-cn.com/problems/shortest-completing-word/
func ShortestCompletingWord(licensePlate string, words []string) string {
	parse := func(str string) (int, map[rune]int) {
		l, m := 0, make(map[rune]int)
		for _, v := range str {
			if (v >= 'A' && v <= 'Z') || (v >= 'a' && v <= 'z') {
				if v > 'Z' {
					v -= 32
				}
				m[v]++
				l++
			}
		}
		return l, m
	}
	l, m := parse(licensePlate)
	contain := func(str string) bool {
		strL, strM := parse(str)
		if strL < l {
			return false
		}
		for k := range m {
			if strM[k] < m[k] {
				return false
			}
		}
		return true
	}
	min, res := 0, ``
	for _, word := range words {
		if len(word) >= l {
			if contain(word) {
				if min == 0 || min > len(word) {
					min, res = len(word), word
				}
			}
		}
	}
	return res
}

// 766
// https://leetcode-cn.com/problems/toeplitz-matrix/
func IsToeplitzMatrix(matrix [][]int) bool {
	if len(matrix) <= 1 || len(matrix[0]) <= 1 {
		return true
	}
	m, n := len(matrix), len(matrix[0])
	isToe := func(x, y int) bool {
		num := matrix[x][y]
		x++
		y++
		for x < m && y < n {
			if matrix[x][y] != num {
				return false
			}
			x++
			y++
		}
		return true
	}
	for i := 0; i < m; i++ {
		if !isToe(i, 0) {
			return false
		}
	}
	for i := 0; i < n; i++ {
		if !isToe(0, i) {
			return false
		}
	}

	return true
}

// 771
// https://leetcode-cn.com/problems/jewels-and-stones/
func NumJewelsInStones(J string, S string) int {
	var JJ = make(map[byte]struct{})
	var val = struct{}{}
	for i := 0; i < len(J); i++ {
		JJ[J[i]] = val
	}
	var res = 0
	for i := 0; i < len(S); i++ {
		if _, ok := JJ[S[i]]; ok {
			res++
		}
	}
	return res
}

// 781
// https://leetcode-cn.com/problems/rabbits-in-forest/
func NumRabbits(answers []int) int {
	m := make(map[int]int)
	res := 0
	for _, v := range answers {
		if _, ok := m[v]; !ok {
			m[v] = 0
		}
		m[v]++
	}
	for k, v := range m {
		res += v / (k + 1) * (k + 1)
		if v%(k+1) != 0 {
			res += k + 1
		}
	}
	return res
}

// 783
// https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
func MinDiffInBST(root *TreeNode) int {
	var arr []int
	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node != nil {
			dfs(node.Left)
			arr = append(arr, node.Val)
			dfs(node.Right)
		}
	}
	dfs(root)
	min := 500001
	for i := 1; i < len(arr); i++ {
		if min > arr[i]-arr[i-1] {
			min = arr[i] - arr[i-1]
		}
	}
	return min
}

// 796
// https://leetcode-cn.com/problems/rotate-string/
func RotateString(A string, B string) bool {
	m, n := len(A), len(B)
	if m != n {
		return false
	}
	if m == 0 {
		return true
	}
	for i := 0; i < len(B); i++ {
		if strings.EqualFold(A, strings.Join([]string{B[i:], B[:i]}, ``)) {
			return true
		}
	}
	return false
}
